package com.example.dynamicprogramming41;

/**
 * @description 动态规划-状态转移方程哈
 * @auther lijiewei
 * @date 2022/4/9 17:32
 */
public class DynamicProgramming2 {

    private int[][] matrix = {{1,3,5,9}, {2,1,3,4}, {5,2,6,7}, {6,8,4,3}};
    private int n = 4;
    private int[][] mem = new int[4][4];



    /**
     * 求最短路径（递归加备忘录法）
     * @param i 行序列
     * @param j 列序列
     * @return
     * @author lijiewei
     * @date   2022/4/12 17:46
     */
    public int minDist(int i, int j) {
        if (i==0 && j==0) {
            return matrix[0][0];
        }
        if (mem[i][j] > 0) {
            return mem[i][j];
        }
        int minLeft = Integer.MAX_VALUE;
        if (j-1>=0) {
            minLeft = minDist(i, j-1);
        }
        int minUp = Integer.MAX_VALUE;
        if(i-1 >=0) {
            minUp = minDist(i-1, j);
        }
        int currMinDist = matrix[i][j]+Math.min(minLeft,minUp);
        mem[i][j] = currMinDist;
        return currMinDist;
    }


}
